# Copyright (c) 2019 Red Hat, Inc. All rights reserved. This copyrighted
# material is made available to anyone wishing to use, modify, copy, or
# redistribute it subject to the terms and conditions of the GNU General Public
# License v.2 or later.
#
# This program is distributed in the hope that it will be useful, but WITHOUT
# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
# details.
#
# You should have received a copy of the GNU General Public License along with
# this program; if not, write to the Free Software Foundation, Inc., 51
# Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
"""KPET data."""

from functools import reduce
import os
import re

from kpet import host_condition
from kpet.misc import attr_parentage
from kpet.schema import Boolean
from kpet.schema import Choice
from kpet.schema import Class
from kpet.schema import Dict
from kpet.schema import Int
from kpet.schema import Invalid
from kpet.schema import List
from kpet.schema import MultiRegex
from kpet.schema import NOTHING
from kpet.schema import Object
from kpet.schema import Reduction
from kpet.schema import Regex
from kpet.schema import RelativeFilePath
from kpet.schema import ScopedYAMLFile
from kpet.schema import String
from kpet.schema import Struct
from kpet.schema import StructObject
from kpet.schema import YAMLFile

# TODO: Make the module shorter, but meanwhile, pylint: disable=too-many-lines


# Schema for universal IDs
UNIVERSAL_ID_SCHEMA = String(pattern="[.a-zA-Z0-9_-]*")

# Schema for domain names
DOMAIN_NAME_SCHEMA = String(pattern="[a-zA-Z0-9_-]+")


def regexes_select_set(regexes, str_set,
                       strict=False,
                       regex_desc='regular expression',
                       str_set_desc='strings'):
    """
    Select a subset of a set of strings using a sequence of regexes.

    Args:
        regexes:        An iterable returning the regular expressions to
                        select by. Each regex will be fully-matched against
                        the strings.
        str_set:        The set of strings to select from.
        strict:         True if an Invalid exception should be raised when a
                        regular expression matches none of the strings from
                        the set. False otherwise.
                        The exception will have the error message generated
                        using "regex_desc" and "str_set_desc".
        regex_desc:     The human-readable description of any regular
                        expression in the list.
        str_set_desc:   The human-readable description of the string set.

    Returns:
        The selected set of strings.

    Raises:
        Invalid, if "strict" is True and any of the regular expressions in the
        list are not matching any strings in the set.
    """
    assert isinstance(str_set, set)
    assert all(isinstance(s, str) for s in str_set)
    assert isinstance(strict, bool)
    assert isinstance(regex_desc, str)
    assert isinstance(str_set_desc, str)

    selected_str_set = set()
    for regex in regexes:
        assert isinstance(regex, re.Pattern)
        regex_str_set = set(filter(regex.fullmatch, str_set))
        if strict and not regex_str_set:
            raise Invalid(
                f"{regex_desc.capitalize()} {regex.pattern!r} matches "
                f"none of the {str_set_desc}: {str_set}"
            )
        selected_str_set |= regex_str_set

    assert isinstance(selected_str_set, set)
    assert all(isinstance(s, str) for s in selected_str_set)
    return selected_str_set


def regexes_reject_set(regexes, str_set):
    """
    Reject a subset of a set of strings using a sequence of regexes.

    Args:
        regexes:        An iterable returning the regular expressions to
                        reject by. Each regex will be fully-matched against
                        the strings.
        str_set:        The set of strings to reject from.

    Returns:
        The set without rejected strings.
    """
    assert isinstance(str_set, set)
    assert all(isinstance(s, str) for s in str_set)
    rejected_str_set = str_set - regexes_select_set(regexes, str_set)
    assert isinstance(rejected_str_set, set)
    assert all(isinstance(s, str) for s in rejected_str_set)
    return rejected_str_set


class Target:  # pylint: disable=too-few-public-methods
    """
    Execution target which case patterns match against.

    A target is describing a single execution of a test.

    A target has a fixed collection of parameters, each of which can be
    assigned a target set.

    A target set is either:

        - a set of strings,
        - None, meaning any possible set of strings.
    """

    @staticmethod
    def set_is_valid(target_set):
        """
        Check if a target set is valid.

        Args:
            target_set: The target set to check.

        Returns:
            True if the target set is valid, false otherwise.
        """
        return target_set is None or \
            (isinstance(target_set, set) and
             all(isinstance(x, str) for x in target_set))

    @staticmethod
    def set_is_unit(target_set):
        """
        Check if a target set is a unit set (has only one member).

        Args:
            target_set: The target set to check.

        Returns:
            True if the target set is a unit set, false otherwise.
        """
        return isinstance(target_set, set) and len(target_set) == 1

    def __init__(self, trees=None, arches=None, components=None):
        """
        Initialize a target.

        Args:
            trees:          A target set of names of the kernel trees we're
                            executing against.
                            Can only be a unit set or None.
            arches:         A target set of names of the architectures we're
                            executing on. Can only be a unit set or None.
            components:     A target set of names of extra components included
                            into the tested kernel build.
        """
        assert Target.set_is_valid(trees)
        assert Target.set_is_unit(trees) or trees is None
        assert Target.set_is_valid(arches)
        assert Target.set_is_unit(arches) or arches is None
        assert Target.set_is_valid(components)

        self.trees = trees
        self.arches = arches
        self.components = components

    def __repr__(self):
        """Print the string representation of the object."""
        attrs = []
        for attr, value in self.__dict__.items():
            value = getattr(self, attr)
            if value is set():
                value_repr = "NONE"
            elif value is None:
                value_repr = "UNKNOWN"
            else:
                value_repr = repr(value)
            attrs.append(attr + "=" + value_repr)
        return "<" + ", ".join(attrs) + ">"


# Pattern's target field qualifiers
PATTERN_QUALIFIERS = {"trees", "arches", "components"}


class PatternOpsOrValues(Choice):
    """Pattern operations or values."""

    def __init__(self):
        """Initialize the schema."""
        super().__init__(
            Regex(),
            List(self),
            Struct(**{k: {self} for k in ("not", "and", "or")})
        )


PATTERN_OPS_OR_VALUES_SCHEMA = PatternOpsOrValues()


class PatternOpsOrQualifiers(Choice):
    """Pattern operations or qualifiers."""

    def __init__(self):
        """Initialize the schema."""
        fields = {}
        fields.update({k: {self} for k in ("not", "and", "or")})
        fields.update({k: {PATTERN_OPS_OR_VALUES_SCHEMA}
                       for k in PATTERN_QUALIFIERS})
        super().__init__(List(self), Struct(**fields))


PATTERN_OPS_OR_QUALIFIERS_SCHEMA = PatternOpsOrQualifiers()


class Pattern(Object):  # pylint: disable=too-few-public-methods
    """Execution target pattern."""

    # The name of an instance of the object to use in error messages
    NAME = "pattern"

    # The schema of the object data, to be passed to the constructor
    SCHEMA = Choice(PATTERN_OPS_OR_QUALIFIERS_SCHEMA, Boolean())

    """An execution target pattern."""
    def __init__(self, data=True):
        """
        Initialize an execution pattern.

        Args:
            data:       Pattern data.
        """
        super().__init__(data)
        self.data = self.SCHEMA.resolve(data)

    # Documentation overhead for multiple functions would be too big, and
    # spread-out logic too hard to grasp.
    # pylint: disable=too-many-branches
    def __node_matches(self, target, and_op, node, qualifier):
        """
        Check if a pattern node matches a target.

        Args:
            target:     The target (an instance of Target) to match.
            and_op:     True if the node items should be "and'ed" together,
                        False if "or'ed".
            node:       The pattern node matching against the target.
                        Either None, a regex, a dictionary or a list.
            qualifier:  Qualifier (name of the target parameter being
                        matched), if already encountered, None if not.
                        Cannot be None if node is a None or a regex.

        Returns:
            True if the node matched, False if not,
            and None if the result could be any.
        """
        assert isinstance(target, Target)
        assert and_op in (False, True)
        assert qualifier is None or qualifier in PATTERN_QUALIFIERS

        # The trinary logic truth table for all possible operations/operands.
        # See https://en.wikipedia.org/wiki/Three-valued_logic
        # Indexed as [and_op][x][y].
        truth_table = {
            # OR
            False: {
                False:  {False: False,  None: None,     True: True},
                None:   {False: None,   None: None,     True: True},
                True:   {False: True,   None: True,     True: True},
            },
            # AND
            True: {
                False:  {False: False,  None: False,    True: False},
                None:   {False: False,  None: None,     True: None},
                True:   {False: False,  None: None,     True: True},
            },
        }

        def sub_op(result_x, result_y):
            """Combine two sub-results using the specified operation."""
            assert result_x in (False, None, True)
            assert result_y in (False, None, True)
            return truth_table[and_op][result_x][result_y]

        if isinstance(node, dict):
            sub_results = []
            for name, sub_node in node.items():
                assert qualifier is None or name not in PATTERN_QUALIFIERS, \
                       "Qualifier is already specified"
                sub_result = self.__node_matches(
                    target, (name != "or"), sub_node,
                    name if name in PATTERN_QUALIFIERS else qualifier)
                if sub_result is not None and name == "not":
                    sub_result = not sub_result
                sub_results.append(sub_result)
            result = reduce(sub_op, sub_results) if sub_results else and_op
        elif isinstance(node, list):
            sub_results = [
                self.__node_matches(target, True, sub_node, qualifier)
                for sub_node in node
            ]
            result = reduce(sub_op, sub_results) if sub_results else and_op
        elif isinstance(node, re.Pattern):
            assert qualifier is not None, "Qualifier not specified"
            param = getattr(target, qualifier)
            if param is None:
                result = None
            else:
                for value in param:
                    if node.fullmatch(value):
                        result = True
                        break
                else:
                    result = False
        else:
            assert False, "Unknown node type: " + type(node).__name__

        return result

    def matches(self, target):
        """
        Check if the pattern matches a target.

        Args:
            target: The target (an instance of Target) to match.

        Returns:
            True if the pattern matches the target, False if not.
        """
        assert isinstance(target, Target)
        if isinstance(self.data, bool):
            return self.data
        node_matches = self.__node_matches(target, True, self.data, None)
        return node_matches is None or node_matches


class Case(StructObject):     # pylint: disable=too-few-public-methods
    """Universal test case."""

    # The name of an instance of the object to use in error messages
    NAME = "test case"

    # The schema of the object data, must recognize to a Struct
    # Defined below, since it's recursive
    SCHEMA = NOTHING

    def __init__(self, data):
        """Initialize the case."""
        super().__init__(data)
        self.id = None
        self.parent = None
        if self.cases is not None:
            for id, case in self.cases.items():
                case.id = id
                case.parent = self


# Case's (recursive) schema, must recognize to a Struct
Case.SCHEMA = Struct(
    name=[String()],
    universal_id=[UNIVERSAL_ID_SCHEMA],
    origin=[String()],
    location=[String()],
    max_duration_seconds=[Int()],
    host_types=[Regex()],
    host_requires=[String()],
    partitions=[String()],
    kickstart=[String()],
    sets=[MultiRegex()],
    high_cost=[Boolean()],
    trigger_sources=[MultiRegex()],
    target_sources=[MultiRegex()],
    enabled=(Class(Pattern), Pattern),
    waived=[Class(Pattern)],
    role=[String()],
    environment=(Dict(String()), dict),
    maintainers=(
        List(Struct(
            name=String(),
            email=String(),
            gitlab={String()},
        )),
        list
    ),
    cases=[Dict(key_schema=String(pattern="[a-zA-Z0-9_-]*"),
                value_schema=Choice(YAMLFile(Class(Case)),
                                    Class(Case)))]
)


class Test:
    # pylint: disable=too-many-instance-attributes
    """A test run - an instance of a test case."""

    def __init__(self, case):
        """
        Initialize a test run as an instance of a test case.

        Args:
            case:           The test case to instantiate.
        """
        assert isinstance(case, Case)

        self.case = case
        self.name = " - ".join(
            reversed(tuple(attr_parentage(case, "name")))
        )
        self.universal_id = next(
            attr_parentage(case, "universal_id"), None
        )
        self.origin = next(attr_parentage(case, "origin"), None)
        self.location = next(attr_parentage(case, "location"), None)
        self.max_duration_seconds = next(
            attr_parentage(case, "max_duration_seconds"), None
        )
        self.host_types = next(
            attr_parentage(case, "host_types"), None
        )
        self.role = next(attr_parentage(case, "role"), "STANDALONE")
        self.environment = reduce(
            lambda x, y: {**y, **x}, attr_parentage(case, "environment"),
            {}
        )
        self.maintainers = reduce(
            lambda x, y: y + x, attr_parentage(case, "maintainers"), []
        )
        self.sets = case.sets or set()
        self.high_cost = next(attr_parentage(case, "high_cost"), None)
        self.trigger_sources = reduce(
            lambda x, y: y + (x or []),
            attr_parentage(case, "trigger_sources"),
            None
        )
        self.target_sources = reduce(
            lambda x, y: y + (x or []),
            attr_parentage(case, "target_sources"),
            None
        )

    def is_enabled_for(self, target):
        """
        Check if the test is enabled for a target.

        Args:
            target: The target to check against.

        Returns:
            True if the test is enabled for the target, False otherwise.
        """
        return all(enabled.matches(target)
                   for enabled in attr_parentage(self.case, "enabled"))

    def is_waived_for(self, target):
        """
        Check if the test is waived for a target.

        Args:
            target: The target to check against.

        Returns:
            True if the test is waived for the target, False otherwise.
        """
        return next(
            attr_parentage(self.case, "waived"), Pattern(False)
        ).matches(target)

    def has_extra_coverage(self):
        """
        Check if the test covers something outside the source tree.

        Returns:
            True if the test covers something outside the source tree.
            False, if not.
        """
        return self.trigger_sources is None and self.target_sources is None

    def select_targeted_sources(self, sources):
        """
        Select sources targeted by the test.

        Select sources targeted by the test (matching "target_sources"
        patterns) from the specified set of source paths.

        Args:
            sources:    The set of sources to select from, or None, if it's
                        unknown.

        Returns:
            A set of sources selected as targeted, or None, if "sources" was
            None.
        """
        assert sources is None or \
            isinstance(sources, set) and \
            all(isinstance(s, str) for s in sources)
        if sources is None:
            return None
        return regexes_select_set(self.target_sources or [], sources)

    def select_triggered_sources(self, sources):
        """
        Select sources triggering the test.

        Select sources triggering the test (matching either "target_sources"
        or "trigger_sources" patterns) from the specified set of source paths.

        Args:
            sources:    The set of sources to select from, or None, if it's
                        unknown.

        Returns:
            A set of sources selected as triggering, or None, if "sources" was
            None.
        """
        assert sources is None or \
            isinstance(sources, set) and \
            all(isinstance(s, str) for s in sources)
        if sources is None:
            return None
        return regexes_select_set(
            (self.target_sources or []) + (self.trigger_sources or []),
            sources
        )


class Domain(StructObject):
    """Host domain."""

    # The name of an instance of the object to use in error messages
    NAME = "domain"

    # A path to a Jinja2 template file rendering into a host_requires XML
    # snippet for this domain, or True, meaning that host_requires is
    # explicitly an exclusion of all peers' host_requires, and not a
    # combination of children's host_requires which happens when the field
    # is False, or is simply omitted.
    host_requires_schema = Choice(String(), Boolean())

    # The schema of the object data, must recognize to a Struct
    # Defined below, since it's recursive
    SCHEMA = NOTHING

    def set_parent_and_name(self, parent, name):
        """
        Set the domain's parent and name, propagating to subdomains.

        Args:
            parent: The parent domain, or None, if none.
            name:   The domain's name.
        """
        assert parent is None or isinstance(parent, Domain)
        assert isinstance(name, str)
        self.parent = parent
        self.name = name
        self.path = ("" if parent is None else parent.path) + "/" + name
        for subdomain_name, subdomain in self.domains.items():
            subdomain.set_parent_and_name(self, subdomain_name)

    def __init__(self, data):
        """Initialize a domain."""
        super().__init__(data)
        # The domain's parent domain, to be set by self.set_parent_and_name()
        self.parent = None
        # The domain's full path, to be set by self.set_parent_and_name()
        self.path = None
        # The domain's name, to be set by self.set_parent_and_name()
        self.name = None
        # A set of hostnames of some of the member hosts.
        # I.e. a set of forced hostnames member host types are using.
        # To be filled when resolving host types.
        self.hostnames = set()
        # A host condition expression specifying the hosts included into this
        # domain, generated by Base._resolve_domains() and
        # Base._isolate_domains() from the host_requires and member hostnames
        # of this and all related domains.
        self.host_condition = None

    def get_specificity(self):
        """
        Calculate how specific the domain is (how many ancestors it has).

        Returns:
            The number of ancestors the domain has, i.e. how specific it is.
        """
        specificity = 0
        parent = self.parent
        while parent:
            specificity += 1
            parent = parent.parent
        return specificity


# The Domain's (recursive) schema, must recognize to a Struct
Domain.SCHEMA = Struct(
    description=String(),
    host_requires=[Domain.host_requires_schema],
    arches=(MultiRegex(), lambda: [re.compile(".*")]),
    domains=(Dict(key_schema=DOMAIN_NAME_SCHEMA,
                  value_schema=Class(Domain)), dict)
)


# The schema for host type name fragments
HOST_TYPE_NAME_FRAGMENT_SCHEMA = String(r'[A-Za-z0-9_-]+')

# The schema for host type names
HOST_TYPE_NAME_SCHEMA = String(
    HOST_TYPE_NAME_FRAGMENT_SCHEMA.regex.pattern +
    '(/' +
    HOST_TYPE_NAME_FRAGMENT_SCHEMA.regex.pattern +
    ')*'
)


class BasicHost(StructObject):  # pylint: disable=too-few-public-methods
    """Basic host."""

    # The name of an instance of the object to use in error messages
    NAME = "basic host"

    # The schema of the object data, must recognize to a Struct
    SCHEMA = Struct(
        description=[String()],
        ignore_panic=[Boolean()],
        partitions=[String()],
        kickstart=[String()],
        kernel_options=[String()],
        kernel_options_post=[String()],
        preboot_tasks=[String()],
        postboot_tasks=[String()],
    )


class Guest(BasicHost):  # pylint: disable=too-few-public-methods
    """Guest host (VM)."""

    # The name of an instance of the object to use in error messages
    NAME = "guest"

    # The schema of the object data, must recognize to a Struct
    SCHEMA = Struct(
        **BasicHost.SCHEMA.attrs,
        args=String(),
    )


class HostType(BasicHost):  # pylint: disable=too-few-public-methods
    """Host type."""

    # The name of an instance of the object to use in error messages
    NAME = "host type"

    # The schema of the object data, must recognize to a Struct
    SCHEMA = Struct(
        **BasicHost.SCHEMA.attrs,
        domains=[Regex()],
        supported=(Class(Pattern), Pattern),
        host_requires=[String()],
        hostname=[String()],
        guests=(Dict(key_schema=HOST_TYPE_NAME_FRAGMENT_SCHEMA,
                     value_schema=Class(Guest)), dict),
    )


class Component(StructObject):     # pylint: disable=too-few-public-methods
    """Build component."""

    # The name of an instance of the object to use in error messages
    NAME = "component"

    # The schema of the object data, must recognize to a Struct
    SCHEMA = Struct(
        description=String(),
        host_requires=[String()],
        supported=(Class(Pattern), Pattern),
    )


# The schema for XML schema file paths
# NOTE: Scenario.generate() expects valid extensions
SCHEMA_PATH_SCHEMA = RelativeFilePath(pattern=r".*\.(xsd|rng|sch)$")


class Base(StructObject):
    # pylint: disable=too-many-instance-attributes
    """Database."""

    # The name of an instance of the object to use in error messages
    NAME = "database"

    # The schema of the object data, must recognize to a Struct
    SCHEMA = ScopedYAMLFile(
        Struct(
            template=[String()],
            schemas=(Reduction(SCHEMA_PATH_SCHEMA,
                               lambda s: [s],
                               List(SCHEMA_PATH_SCHEMA)), list),
            trees=(Dict(Struct(arches={MultiRegex()})), dict),
            arches=(List(String()), list),
            components=(Dict(Class(Component)), dict),
            sets=(Dict(String()), dict),
            domains=[Dict(key_schema=DOMAIN_NAME_SCHEMA,
                          value_schema=Class(Domain))],
            host_types=[Dict(key_schema=HOST_TYPE_NAME_FRAGMENT_SCHEMA,
                             value_schema=Class(HostType))],
            recipesets=(Dict(List(HOST_TYPE_NAME_FRAGMENT_SCHEMA)), dict),
            variables=(Dict(
                Struct(
                    description=String(),
                    type={String(r'str|bool')},
                    default={Choice(String(), Boolean())},
                )
            ), dict),
            origins=[Dict(String())],
            not_sources=(MultiRegex(), list),
            case=[Choice(YAMLFile(Class(Case)), Class(Case))]
        )
    )

    @staticmethod
    def is_dir_valid(dir_path):
        """
        Check if a directory is a valid database.

        Args:
            dir_path:   Path to the directory to check.

        Returns:
            True if the directory is a valid database directory,
            False otherwise.
        """
        return os.path.isfile(dir_path + "/index.yaml")

    # pylint: disable=too-many-branches
    def _case_resolve(self, case, sets):
        """
        Validate and resolve a case and its sub-cases.

        Args:
            case:   The case to resolve.
            sets:   A set of names of sets the case can belong to, or None,
                    if it isn't defined and self.sets should be used.
        """
        assert isinstance(case, Case)
        assert sets is None or \
            isinstance(sets, set) and \
            all(isinstance(set_name, str) for set_name in sets)

        if case.parent:
            if case.parent.parent:
                case.path = case.parent.path + "/" + case.id
            else:
                case.path = "/" + case.id
            case.ref = f"case {case.path}"
        else:
            case.path = "/"
            case.ref = "the root case"

        # Check host_types matches something
        host_type_names = []
        for host_type_name, host_type_data in (self.host_types or {}).items():
            host_type_names.append(host_type_name)
            for guest_name in host_type_data.guests:
                host_type_names.append(host_type_name + '/' + guest_name)
        if case.host_types is not None and \
           not any(case.host_types.fullmatch(name)
                   for name in host_type_names):
            raise Invalid(f'Host type regex "{case.host_types.pattern}" '
                          f'of {case.ref} does not match any of the '
                          f'available host type names: {host_type_names}')

        # Check case origin is valid
        if self.origins is None:
            if case.origin is not None:
                raise Invalid(
                    f'{case.ref.capitalize()} has origin specified, '
                    f'but available origins are not defined in '
                    f'the database.'
                )
        else:
            if case.origin is not None and \
               case.origin not in self.origins:
                raise Invalid(
                    f'{case.ref.capitalize()} has unknown origin '
                    f'specified: "{case.origin}".\n'
                    f'Expecting one of the following: '
                    f'{", ".join(self.origins.keys())}.'
                )

        # Resolve set regexes into set names
        if case.sets is None:
            case.sets = sets
        else:
            case.sets = regexes_select_set(
                case.sets,
                set(self.sets) if sets is None else sets,
                strict=True,
                regex_desc=f"{case.ref} set regex",
                str_set_desc="available sets",
            )
            sets = case.sets

        # Resolve sub-cases if any
        for subcase in (case.cases or {}).values():
            self._case_resolve(subcase, sets)

    def _case_render_tests(self, case, tests):
        """
        Render tests for a case and its children.

        Args:
            case:   The case to render the tests for.
            tests:  The dictionary to store rendered tests in.
        """
        assert isinstance(tests, dict)
        assert all(
            isinstance(name, str) and isinstance(test, Test)
            for name, test in tests.items()
        )
        assert isinstance(case, Case)

        # If this is a test case (a leaf node)
        if case.cases is None:
            # Create the test
            test = Test(case)
            # Check the test name is unique
            if test.name in tests:
                raise Invalid(f"Test for {case.ref} has a non-unique name: "
                              f"{test.name}")
            # Check the test has at least one maintainer
            if not test.maintainers:
                raise Invalid(f"Test \"{test.name}\" "
                              f"for {case.ref} has no maintainers")
            # Check the test has an universal_id
            if test.universal_id is None:
                raise Invalid(f"Test \"{test.name}\" "
                              f"for {case.ref} has no universal_id specified")
            # Check the test has an origin, if needed
            if self.origins is not None and test.origin is None:
                raise Invalid(f"Test \"{test.name}\" "
                              f"for {case.ref} has no origin specified")
            # Add the test
            tests[test.name] = test
        # Else it's an abstract case
        else:
            # Render tests for sub-cases
            for subcase in case.cases.values():
                self._case_render_tests(subcase, tests)

    def _resolve_tree_arches(self):
        """
        Resolve tree arches.

        Resolve each tree's supported architecture specification from
        a list of regexes to a list of architecture names matching those
        regexes

        Returns:
            Raises a schema.Invalid exception when finding an invalid regex
        """
        wildcard = [re.compile(".*")]
        for name, value in self.trees.items():
            value["arches"] = list(regexes_select_set(
                value.get("arches", wildcard),
                set(self.arches),
                strict=True,
                regex_desc=f"tree {name!r} architecture regex",
                str_set_desc="available architectures"
            ))

    def _resolve_host_types(self):
        """Resolve host type links to other parts of the database."""
        for host_type_name, host_type in (self.host_types or {}).items():
            if host_type.domains is None:
                host_type.domains = {}
            else:
                if self.domains is None:
                    raise Exception(f"Host type {host_type_name!r} specifies "
                                    f"\"domains\" but domains are not "
                                    f"defined")
                domains_re = host_type.domains
                host_type.domains = {
                    path: domain
                    for path, domain in self.all_domains.items()
                    if domains_re.fullmatch(path) or
                    domains_re.fullmatch(domain.name)
                }
                if not host_type.domains:
                    raise Exception(
                        f"Host type {host_type_name!r} specifies "
                        f"a \"domains\" regex "
                        f"{domains_re.pattern!r} "
                        f"that matches none of the known "
                        f"domain paths: {set(self.all_domains)!r}"
                        f" or domain names: "
                        f"{set(d.name for d in self.all_domains.values())!r}"
                    )
                # Distribute forced hostname to domains, if any
                if host_type.hostname is not None:
                    for domain in host_type.domains.values():
                        while domain:
                            domain.hostnames.add(host_type.hostname)
                            domain = domain.parent

    @staticmethod
    def _resolve_domains(domains, arches):
        """
        Resolve domain links to other parts of the database.

        Args:
            domains:    The dictionary of domains to resolve.
            arches:     A set of architectures available for resolution.
        """
        assert isinstance(domains, dict)
        assert all(isinstance(name, str) and isinstance(domain, Domain)
                   for name, domain in domains.items())
        assert isinstance(arches, set)
        assert all(isinstance(arch, str) for arch in arches)

        got_true_host_requires = False
        for domain_name, domain in domains.items():
            # Resolve architectures
            domain_arches = regexes_select_set(
                domain.arches,
                arches,
                strict=True,
                regex_desc=f"domain {domain_name!r} architecture regex",
                str_set_desc="available architectures"
            )
            domain.arches = list(domain_arches)
            # Resolve subdomains
            Base._resolve_domains(domain.domains, domain_arches)
            # If the domain has host requires template specified
            if isinstance(domain.host_requires, str):
                condition = "T:" + domain.host_requires
            # Else, if its condition is solely the inverse of its peers
            elif domain.host_requires:
                if got_true_host_requires:
                    raise Exception(
                        f"Domain {domain_name!r} has peer-exclusive host "
                        f"requirements ('host_requires: true'), but another "
                        f"peer has that too."
                    )
                got_true_host_requires = True
                # Leave it for _isolate_domains() to add peer exclusion
                condition = []
            # Else its condition is the conjunction of children conditions
            else:
                condition = {"or": [
                    subdomain.host_condition
                    for subdomain in domain.domains.values()
                ]}
            assert domain.host_condition is None
            domain.host_condition = condition
            assert host_condition.is_valid(domain.host_condition)

    @staticmethod
    def _isolate_domains(domains):
        """
        Isolate domains from each other.

        Expand host condition expressions of each domain (and its subdomains)
        in a dictionary, to exclude hosts of all its peers, to make sure each
        domain is isolated.

        Args:
            domains:    The dictionary of peer domains to isolate.
        """
        assert isinstance(domains, dict)
        assert all(
            isinstance(k, str) and isinstance(v, Domain)
            for k, v in domains.items()
        )
        peer_conditions = []
        # Collect peer conditions, together with their forced hostnames
        for domain in domains.values():
            # Isolate subdomains
            Base._isolate_domains(domain.domains)
            # Collect peers' conditions and forced hostnames
            domain_peer_conditions = []
            for other_domain in domains.values():
                if other_domain is not domain:
                    domain_peer_conditions.append(other_domain.host_condition)
                    for hostname in other_domain.hostnames:
                        if hostname not in domain.hostnames:
                            domain_peer_conditions.append("H:" + hostname)
            peer_conditions.append(domain_peer_conditions)
        # Distribute peer conditions
        for domain in domains.values():
            domain.host_condition = [
                domain.host_condition,
                {"not": {"or": peer_conditions.pop(0)}}
            ]
            assert host_condition.is_valid(domain.host_condition)

    def _validate_recipesets(self):
        """Check recipesets refer to existing host types."""
        for recipeset_name, recipeset_host_type_names \
                in self.recipesets.items():
            for host_type_name in recipeset_host_type_names:
                if host_type_name not in self.host_types:
                    raise Exception(
                        f"Recipeset {recipeset_name!r} refers "
                        f"to unknown host type {host_type_name!r}"
                    )

    @staticmethod
    def variable_value_parse(variable, string):
        """
        Parse a string as a value for a variable.

        Args:
            variable:   The definition object for the variable to parse the
                        value for.
            string:     The string representation of the variable's value to
                        parse.

        Returns:
            The parsed variable's value, or None if the value was invalid.
        """
        assert isinstance(variable, dict)
        assert 'type' in variable
        assert variable['type'] in (str, bool)

        if variable['type'] == str:
            value = string
        elif variable['type'] == bool:
            value = {
                "true": True,
                "True": True,
                "false": False,
                "False": False
            }.get(string, None)
        else:
            value = None

        assert isinstance(value, (type(None), variable['type']))
        return value

    def select_sources(self, files):
        """
        Select sources from a set of file paths.

        Select paths to the source files that the tests in the database could
        cover from the supplied set of file paths.

        Args:
            files:  The set of file paths to select from, or None, if it's
                    unknown.

        Returns:
            A set of selected source file paths, or None, if "files" was None.
        """
        assert files is None or \
            isinstance(files, set) and \
            all(isinstance(s, str) for s in files)
        if files is None:
            return None
        return \
            regexes_reject_set(self.not_sources, files) | \
            regexes_select_set(self.sources, files)

    def __init__(self, dir_path):
        """Initialize a database object."""
        assert self.is_dir_valid(dir_path)
        try:
            super().__init__(dir_path + "/index.yaml")
        except Invalid as exc:
            raise Invalid(f"Invalid {self.NAME}") from exc
        self.dir_path = dir_path
        for name, variable in self.variables.items():
            variable['type'] = {
                "str": str,
                "bool": bool,
            }[variable.get('type', 'str')]
            if 'default' in variable and \
                    not isinstance(variable['default'], variable['type']):
                raise Invalid(f"The default value {variable['default']!r} "
                              f"of variable {name!r} doesn't match its type "
                              f"{variable['type'].__name__!r}")
        self._resolve_tree_arches()
        # Propagate domain names and paths,
        # to be used by _resolve_host_types()
        for domain_name, domain in (self.domains or {}).items():
            domain.set_parent_and_name(None, domain_name)
        # Collect all domains into a flat path-indexed dictionary
        if self.domains is None:
            self.all_domains = None
        else:
            def collect_domains(domains):
                collected_domains = {}
                for domain in domains.values():
                    collected_domains[domain.path] = domain
                    collected_domains = {
                        **collected_domains,
                        **collect_domains(domain.domains)
                    }
                return collected_domains
            self.all_domains = collect_domains(self.domains)
        self._resolve_host_types()
        if self.domains is not None:
            Base._resolve_domains(self.domains, set(self.arches))
            Base._isolate_domains(self.domains)
        # Validate recipesets
        self._validate_recipesets()
        # Render tests from cases
        self.tests = {}
        if self.case is not None:
            self._case_resolve(self.case, None)
            self._case_render_tests(self.case, self.tests)
        # Collect all source regexes from tests
        # TODO: Consider compiling a single regex instead
        self.sources = {
            regex
            for test in self.tests.values()
            for regex in (
                (test.trigger_sources or []) + (test.target_sources or [])
            )
        }
